package com.cqs.leetcode.dp;

import com.cqs.leetcode.TreeNode;



/**
 * @author lixiaowen
 * @create 2019-12-13
 */
public class HouseRobberII337 {


    public int rob(TreeNode root) {
        if (root == null ) return 0;
        if (root.left==null && root.right == null) return root.val;
        TreeNode left = root.left;
        int l = 0, r = 0,  ll = 0,lr = 0;
        if (left != null) {
            //更新left.val保存中间结果
            l = left.val = rob(left);
            //使用了中间结果
            if (left.left != null) ll = left.left.val;
            if (left.right != null) lr = left.right.val;
        }
        TreeNode right = root.right;
        int rl = 0,rr = 0;
        if (right != null) {
            r = right.val = rob(right);
            if (right.left != null) rl = right.left.val;
            if (right.right != null) rr = right.right.val;
        }
        return root.val = Math.max(ll + lr + rl + rr + root.val, l + r);
    }


}
